/*
题目: 和为奇数的子数组个数
给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。

由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
 */
public class OddNumOfSubarrays {
    public int numOfSubarrays(int[] arr) {
        // 前缀和
        int sum = 0, n = arr.length;
        int mod = (int) (1e9 + 7);

        int odd = 0, even = 0; // 定义奇数, 偶数前缀和 的数量
        int src = 0;
        for (int i = 0; i < n; i ++) {
            sum += arr[i];
            if ((sum & 1) == 1) { // 如果当前是 奇数
                src += even + 1; // 本身 + 偶数个数
                odd ++;
            } else {  // 如果当前是偶数
                src += odd;   // 奇数个数
                even ++;
            }

            src %= mod;
        }
        return src;
    }
}
